`
https://leetcode.cn/problems/predict-the-winner/
`

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var predictTheWinner = function (nums) {
  return stoneGame(nums) >= 0
};

function stoneGame(nums) {
  const n = nums.length

  // dp[i][j].fir = x 表示，对于 nums[i...j] 这部分石头堆，先手能获得的最高分数为 x
  // dp[i][j].sec = y 表示，对于 nums[i...j] 这部分石头堆，后手能获得的最高分数为 y
  const dp = Array.from({ length: n }, () => Array.from({ length: n }, () => new Pair(0, 0)))

  // 填入 base case
  for (let i = 0; i < n; i++) {
    dp[i][i].fir = nums[i]
    dp[i][i].sec = 0
  }

  // 倒着遍历数组
  for (let i = n - 2; i >= 0; i--) {
    for (let j = i + 1; j < n; j++) {
      // 先手选择最左边或最右边的分数
      const left = nums[i] + dp[i + 1][j].sec
      const right = nums[j] + dp[i][j - 1].sec
      // 套用状态转移方程
      // 先手肯定会选择更大的结果，后手的选择随之改变
      if (left > right) {
        dp[i][j].fir = left
        dp[i][j].sec = dp[i + 1][j].fir
      } else {
        dp[i][j].fir = right
        dp[i][j].sec = dp[i][j - 1].fir
      }
    }
  }

  const res = dp[0][n - 1]
  return res.fir - res.sec
}

function Pair(fir, sec) {
  this.fir = fir
  this.sec = sec
}